package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * str
 * 955. 删列造序 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/24 17:50
 */
public class MinDeletionSize {

    public static void main(String[] args) {
        MinDeletionSize test = new MinDeletionSize();


        // 1
//        String[] arr = {"ca","bb","ac"};

        // 0
//        String[] arr = {"xc","yb","za"};

        // 3
        String[] arr = {"zyx", "wvu", "tsr"};

        int i = test.minDeletionSize(arr);
        System.out.println(i);
    }


    public int minDeletionSize(String[] strs) {
        int a = strs.length;
        int b = strs[0].length();
        int[] arr1 = new int[a];
        int[] arr2 = new int[a];
        int count = 0;
        for (int i = 0; i < b; i++) {
            char item = 'a';
            for (int j = 0; j < a; j++) {
                char c = strs[j].charAt(i);
                if (arr1[j] == 1) {
                    item = c;
                    continue;
                }
                if (c < item) {
                    count++;
                    System.arraycopy(arr1, 0, arr2, 0, a);
                    break;
                }
                if (c > item) {
                    arr2[j] = 1;
                }
                item = c;
            }
            System.arraycopy(arr2, 0, arr1, 0, a);
        }
        return count;
    }

}
